package 力扣日常刷题.木22一月.第04天0111;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author 帅小伙
 * @date 2022/1/11
 * @description
 */
public class Demo06回溯组合总和 {


    ArrayList<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        Deque<Integer> path = new ArrayDeque<>();//存储根节点开始的路径
        dfs(1, k, path, n);
        return ans;
    }

     void dfs(int begin, int k, Deque<Integer> path, int target) {
        if (target == 0 && path.size() == k) {
            ans.add(new ArrayList<Integer>(path));
            return;
        }

        for (int i = begin; i < 10; i++) {
            // 大剪枝
            if (target - i < 0) return;
            // 选择
            path.addLast(i);
            dfs(i + 1, k, path, target - i);
            // 撤销选择
            path.removeLast();
        }
    }

}
